package com.order.www;

/**
 * Creared with IntelliJ IDEA.
 * Description:给定一个由非负整数填充的m x n的二维数组，现在要从二维数组的左上角走到右下角，请找出路径上的所有数字之和最小的路径。
 * 注意：你每次只能向下或向右移动。
 * User:yxd
 * Date:2022-03-23
 * Time:22:28
 */
public class Dp7 {
    public int minPathSum (int[][] grid) {
        // write code here
        if(grid == null){
            return -1;
        }
        //状态定义F(i,j) 从左上角到这个点的最小路径
        //状态转移方程F(i,j) = Math.min(F(i - 1,j),F(i,j - 1)) + array[i][j]
        //初值F(0,0) = array[0,0]
        for(int i = 1;i < grid.length ;i ++){
            grid[i][0] = grid[i - 1][0] + grid[i][0];
        }
        for(int i = 1;i < grid[0].length ;i ++){
            grid[0][i] = grid[0][i - 1] + grid[0][i];
        }
        for(int i = 1;i < grid.length;i ++){
            for(int j = 1;j < grid[0].length;j ++){
                grid[i][j] = Math.min(grid[i - 1][j],grid[i][j - 1]) + grid[i][j];
            }
        }
        return grid[grid.length - 1][grid[0].length - 1];
    }
}
